/*
#include<iostream>
using namespace std;
int i[30], j[30], zhu[30], fu[30];
int main() {
    int n = 4;
    int ans = 0;
    for (int j = 1; j <= n; j++) {
        int x1 = 1, y1 = j;
        i[x1] = true;
        j[y1] = true;
        fu[x1 + y1] = true;
        zhu[n - y1 + x1] = true;
        for (int j = 1; j <= n; j++) {
            int x2 = 2, y2 = j;
            if (i[x2] || j[y2] || fu[x2 + y2] || zhu[n - y2 + x2])
                continue;
            i[x2] = true;

            j[y2] = true;
            fu[x2 + y2] = true;
            zhu[n - y2 + x2] = true;
            for (int k = 1; k <= n; k++) {
                int x3 = 3, y3 = k;
                if (i[x3] || j[y3] || fu[x3 + y3] || zhu[n - y3 + x3])
                    continue;
                i[x3] = true;
                j[y3] = true;
                fu[x3 + y3] = true;
                zhu[n - y3 + x3] = true;
                for (int l = 1; l <= n; l++) {
                    int x4 = 4, y4 = l;
                    if (i[x4] || j[y4] || fu[x4 + y4] || zhu[n - y4 +
                        x4]) continue;
                    ans++;
                }
                // 回溯
                i[x3] = false;
                j[y3] = false;
                fu[x3 + y3] = false;
                zhu[n - y3 + x3] = false;
            }
            // 回溯
            i[x2] = false;
            j[y2] = false;
            fu[x2 + y2] = false;
            zhu[n - y2 + x2] = false;
        }
        // 回溯
        i[x1] = false;
        j[y1] = false;
        fu[x1 + y1] = false;
        zhu[n - y1 + x1] = false;
    }
    cout << ans << endl;
    return 0;
}
*/

/*
#include<iostream>
using namespace std;
const int N = 30;
int n;
int col[N], zhu[N], fu[N];
int ans;
void dfs(int i) {
    if (i > n) {
        ans++;
        return;
    }
    for (int j = 1; j <= n; ++j) {
        if (col[j] || zhu[n - j + i] || fu[i + j])
            continue;
        col[j] = 1;
        zhu[n - j + i] = 1;
        fu[i + j] = 1;
        dfs(i + 1);
        col[j] = 0;
        zhu[n - j + i] = 0;
        fu[i + j] = 0;
    }
    return;
}


int main() {

    cin >> n;
    dfs(1);
    cout << ans << endl;
    return 0;
}
*/


/*
#include<iostream>
using namespace std;
int n;
int s[50];

void dfs(int x) {
    if (x > n) {
        for (int i = 1; i <= n; ++i) {
            if(s[i])
                cout << i << " ";
        }
        cout << endl;
        return;
    }
    //s[x] = 0;
    //dfs(x + 1);
    //s[x] = 1;
    //dfs(x + 1);
    for (int i = 0; i <= 1; ++i) {
        s[x] = i;
        dfs(x + 1);
    }

    return;
}

int main() {
    cin >> n;
    dfs(1);

    return 0;
}
*/

/*
#include <iostream>
using namespace std;
#include <algorithm> 
int n, k;
const int N = 20;
int a[N];
int b[N];
int compare = 0;
int ret = 0;

void dfs(int x) {
    if (x > n) {
        int temp = 0;
        compare = 0;
        for (int j = 0; j < n; ++j) {
            temp += b[j] * a[j];           
        }
        if (temp < k)
            compare = temp;
        ret = max(ret, compare);
        return;
    }
    for (int i = 0; i <= 1; ++i) {
        b[x] = i;
        dfs(x + 1);
    }
    return;
}

int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    dfs(0);
    cout << ret << endl;
    return 0;
}
*/

/*
//代码太复杂了，还是需要加上别的东西，裂开(剪枝太粗糙了)
#include <iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int ans;
int nums[101];
int flag[101];

void dfs(int x) {
    int temp_count = 0;
    int temp_one;
    int temp_one_num;
    int temp_two;
    int temp_two_num;
    for (int j = 2; j <= x; ++j) {
        
        if (flag[j] && (temp_count==0)) {
            temp_count++;
            temp_one = nums[j];
            temp_one_num = j;
            continue;
        }
        if (flag[j] && (temp_count == 1)) {
            temp_count++;
            temp_two = nums[j];
            temp_two_num = j;
        }
        if (temp_count == 2) {
            int test = temp_one + temp_two;
            double squareRoot = sqrt(test);
            if (squareRoot == int(squareRoot)) { // 判定不是整数
                //ans++;
                nums[temp_one_num] = nums[temp_two_num] = 0;
                return;
            }
        }
    }
   
    for (int i = x; i < 30; ++i) {
        if (nums[i] != 0) {
            flag[i] = 1;
            dfs(i+1);
            flag[i] = 0;
        }     
    }
    
    return;
}

int main()
{
    for (int i = 1; i <= 30; ++i) {
        if (i == 1 || i == 4 || i == 9 || i == 16 || i == 25 || i == 36 || i == 49 || i == 64 || i == 81 || i == 100)
            continue;
        nums[i] = i;
   }
    dfs(2);
    for (int i = 1; i <= 100; ++i) {
        if (nums[i] != 0)
            ans++;
    }
    cout << ans << endl;
    return 0;
}
*/

/* 
// (1ll*round(fff))会变成科学计数法统计数字,ll wwww 就是默认十进制
#include <iostream>
#include<cmath>
using namespace std;
typedef long long ll;

int main()
{
    int a;
    double b;
    double  fff;
    cin >> a >> b;

    fff = b * (1 << a);
    ll wwww = round(fff);
    cout << "wwww:" << wwww << endl;
    cout << "round(fff):" << (1ll*round(fff)) << endl;
    return 0;
}
*/



//
//记忆化搜索(空间换时间)
//

//斐波拉契序列
/*
#include<iostream>
using namespace std;
int f[50];
int fib(int n) {
    if (n == 1 || n == 2) return 1;
    if (f[n] != -1) return f[n];
    return f[n] = fib(n - 1) + fib(n - 2);
}
int main() {
    memset(f, -1, sizeof(f));
    cout << fib(10);
}
*/

// 01背包
#include<iostream>
using namespace std;
const int N = 1010;
int w[N], v[N];
int dp[N][N];
int n, m;
//1.定义记忆化数组
//2.初始化记忆化数组为 -1（未访问）
//3.搜索的时候记忆
//  - 在递归边界下判断当前状态是否访问过，访问过，直接返回
//  - 没访问过，正常搜索，记忆下来

int dfs(int u, int sum) {
    //u代表当前选择的是第几个物品
   //sum表示当前的总体积
   //递归函数返回值代表最大价值
    if (u > n) {
        return 0;
    }
    if (dp[u][sum] != -1) 
        return dp[u][sum];
    int ans1 = 0;
    int ans2 = dfs(u + 1, sum);               //不选当前物品u，直接进入下一个物品的状态
    if (sum + v[u] <= m)                      //如果选了当前物品，加起来的体积没有超过总体积m
        ans1 = dfs(u + 1, sum + v[u]) + w[u]; // 递归到下一个物品 u + 1，并加上当前物品的价值 w[u]。   

    return dp[u][sum] = max(ans1, ans2);      // 即选择或不选择当前物品的最大价值，并将结果存储到 dp[u][sum] 中
}
int main() {
    memset(dp, -1, sizeof(dp));
    cin >> n >> m;
    for (int i = 1; i <= n; i++) 
        cin >> v[i] >> w[i];
    cout << dfs(1, 0); // dfs(1, 0)是出发时候的状态
}
